package main.java.com.amanda.suafa;

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.utils.Graph;

import java.util.Scanner;

/**
 * @author amanda
 * @Description 算法4.1 深度优先搜索查找图中的途径
 */
public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;       // 从起点到一个顶点的已知路径上的最后一个顶点
    private final int s;        // 起点
    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))
            return null;
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Graph G = new Graph(scanner);
        int s = scanner.nextInt();
        DepthFirstPaths dfs = new DepthFirstPaths(G, s);
        for (int v = 0; v < G.V(); v++) {
            if (dfs.hasPathTo(v)) {
                StdOut.printf("%d to %d:  ", s, v);
                for (int x : dfs.pathTo(v)) {
                    if (x == s)
                        StdOut.print(x);
                    else
                        StdOut.print("-" + x);
                }
                StdOut.println();
            }
            else {
                StdOut.printf("%d to %d:  not connected\n", s, v);
            }
        }
    }
}
/*
6 8 0 5 2 4 2 3 1 2 0 1 3 4 3 5 0 2 0
 */
